﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;

namespace PcMagazineLogicalProcessor
{
    class Program
    {
        static char charPlay;
        static char[,] matrix;
        static List<List<Coordinates>> listWithAllElemetsForRate;
        static readonly object locker = new object();
        static int elementnumber = 0;
        static BestMove bMove;
        static bool haveTime = true;


        static void Main(string[] args)
        {
            bool IsValidInput = true;
            Stopwatch sw = new Stopwatch();
            sw.Start();

            ReadInputMatrix(out IsValidInput);

            if (!IsValidInput)
            {
                return;
            }

            sw.Stop();

            MoveMaker(sw.Elapsed.Milliseconds);
        }



        private static void ReadInputMatrix(out bool isValidInput)
        {
            isValidInput = true;

            int m = 0;
            int n = 0;
            string[] expectedRows;

            try
            {
                string expectedString = Console.ReadLine();
                string[] expectedFirstRow = expectedString.Split(new Char[] { '\n', '\r', ' ' }, StringSplitOptions.RemoveEmptyEntries);


                if (!int.TryParse(expectedFirstRow[0], out m))
                {
                    isValidInput = false;
                }
                if (!int.TryParse(expectedFirstRow[1], out n))
                {
                    isValidInput = false;
                }

                expectedRows = new string[n];
                for (int i = 0; i < n; i++)
                {
                    expectedRows[i] = Console.ReadLine();
                }
                if (!IsValidInput(n, m, expectedRows))
                {
                    isValidInput = false;
                }

                string expectedLastRow = Console.ReadLine();
                string[] lastRowSumbol = expectedLastRow.Split(new Char[] { '\n', '\r', ' ' }, StringSplitOptions.RemoveEmptyEntries);
                charPlay = (lastRowSumbol[0])[0];
               
            }
            catch (Exception)
            {
                isValidInput = false;
                Console.WriteLine("error");
                return;
            }

            if (!isValidInput)
            {
                Console.WriteLine("error");
                return;
            }

            FillMatrix(n, m, expectedRows);
        }

        #region Support Methods For ReadInputMatrix
        private static void FillMatrix(int n, int m, string[] expectedRows)
        {
            char[,] inputMatrix = new char[n, m];
            for (int row = 0; row < n; row++)
            {
                for (int col = 0; col < m; col++)
                {
                    inputMatrix[row, col] = (expectedRows[row])[col];
                }
            }
            matrix = inputMatrix;
        }
        static bool IsValidInput(int n, int m, string[] expectedRows)
        {
            if (n < 3 || n > 20)
            {
                return false;
            }
            if (m < 3 || m > 20)
            {
                return false;
            }
            for (int i = 0; i < n; i++)
            {
                if (expectedRows[i].Length != m)
                {
                    return false;
                }
                for (int j = 0; j < m; j++)
                {
                    string row = expectedRows[i];
                    if (row[j] != 'A' && row[j] != 'B' && row[j] != '-')
                    {
                        return false;
                    }

                }

            }
            return true;

        } 
        #endregion


        private static void MoveMaker(int timeElapsed) 
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            int numberOfCPUCores = Environment.ProcessorCount;

            listWithAllElemetsForRate = MoveGenerator(matrix, charPlay);  
            if (listWithAllElemetsForRate.Count > 0)
            {
                bMove = new BestMove(0, listWithAllElemetsForRate[0]);
            }
            else
            {
                Environment.Exit(0);
                //???????????
            }

            for (int i = 0; i < numberOfCPUCores; i++)
            {
                new Thread(ThreadJoB).Start();
            }

            sw.Stop();

            Thread.Sleep(700 - timeElapsed - sw.Elapsed.Milliseconds);

            PrintMatrix();
            Environment.Exit(0);
            haveTime = false;
        }

        #region Support Methods For MoveMaker
        static void ThreadJoB()
        {
            while (haveTime)
            {
                List<Coordinates> moveForChaeck;
                lock (locker)
                {
                    if (elementnumber < listWithAllElemetsForRate.Count)
                    {
                        moveForChaeck = listWithAllElemetsForRate[elementnumber];
                        elementnumber++;
                    }
                    else
                    {
                        break;
                    }
                }
                char[,] newMatrix = (char[,])matrix.Clone();
                List<float> resultList = new List<float>();
                foreach (Coordinates item in moveForChaeck)
                {
                    newMatrix[item.Row, item.Col] = charPlay;
                }
                if (charPlay == 'A')
                {
                    RecursionCheckMove(newMatrix, 'B', resultList);
                }
                else
                {
                    RecursionCheckMove(newMatrix, 'A', resultList);
                }
                int score = MakeMoveSocre(resultList);

                lock (locker)
                {
                    if (score > bMove.moveScore)
                    {
                        bMove = new BestMove(score, moveForChaeck);
                    }
                }

            }
        }
        static void RecursionCheckMove(char[,] matrix, char player, List<float> result)
        {
            List<List<Coordinates>> bestMovesList = MoveGenerator(matrix, player);
            if (bestMovesList.Count == 0)
            {
                int A = 0;
                int B = 0;
                MatrixCounter(matrix, out A, out B);
                if (charPlay == 'A')
                {
                    if (A > B)
                    {
                        result.Add(1);
                    }
                    else if (A == B)
                    {
                        result.Add(0.5f);
                    }
                    else
                    {
                        result.Add(0);
                    }
                }
                else
                {
                    if (A < B)
                    {
                        result.Add(1);
                    }
                    else if (A == B)
                    {
                        result.Add(0.5f);
                    }
                    else
                    {
                        result.Add(0);
                    }
                }

                return;

            }
            char nextPlayer;
            if (player == 'A')
            {
                nextPlayer = 'B';
            }
            else
            {
                nextPlayer = 'A';
            }

            foreach (List<Coordinates> list in bestMovesList)
            {
                char[,] newMatrix = (char[,])matrix.Clone();

                foreach (Coordinates item in list)
                {
                    newMatrix[item.Row, item.Col] = player;
                }

                RecursionCheckMove(newMatrix, nextPlayer, result);
            }
        }
        private static void MatrixCounter(char[,] matrix, out int A, out int B)
        {
            A = 0;
            B = 0;
            foreach (char ch in matrix)
            {
                if (ch == 'A')
                {
                    A++;
                }
                else
                {
                    B++;
                }
            }

        }
        private static int MakeMoveSocre(List<float> list)
        {
            float sum = 0;
            for (int i = 0; i < list.Count; i++)
            {
                sum += list[i];
            }
            return (int)((sum / list.Count) * 100);
        }
        static List<List<Coordinates>> MoveGenerator(char[,] matrix, char player)
        {

            List<List<Coordinates>> listTriple = new List<List<Coordinates>>();
            List<List<Coordinates>> listTwice = new List<List<Coordinates>>();
            List<List<Coordinates>> listSingle = new List<List<Coordinates>>();

            #region FindListWith 3 2 and 1
            for (byte r = 0; r < matrix.GetLength(0); r++)
            {
                for (byte c = 0; c < matrix.GetLength(1); c++)
                {
                    if (matrix[r, c] != '-') continue;
                    if (c >= 2 && r < (matrix.GetLength(0) - 2))
                    {
                        if (matrix[r, c] == matrix[r + 1, c - 1] && matrix[r, c] == matrix[r + 2, c - 2])
                        {
                            listTriple.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r+1),(byte)(c-1)),
                                                             new Coordinates((byte)(r+2),(byte)(c-2))});
                        }
                    }

                    if (r < (matrix.GetLength(0) - 2) && c < (matrix.GetLength(1) - 2))
                    {
                        if (matrix[r, c] == matrix[r + 1, c + 1] && matrix[r, c] == matrix[r + 2, c + 2])
                        {
                            listTriple.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r+1),(byte)(c+1)),
                                                             new Coordinates((byte)(r+2),(byte)(c+2))});
                        }
                    }

                    if (r < matrix.GetLength(0) - 2)
                    {
                        if (matrix[r, c] == matrix[r + 1, c] && matrix[r, c] == matrix[r + 2, c])
                        {
                            listTriple.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r+1),(byte)(c)),
                                                             new Coordinates((byte)(r+2),(byte)(c))});
                        }
                    }



                    if (c < (matrix.GetLength(1) - 2))
                    {
                        if (matrix[r, c] == matrix[r, c + 1] && matrix[r, c] == matrix[r, c + 2])
                        {
                            listTriple.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r),(byte)(c+1)),
                                                             new Coordinates((byte)(r),(byte)(c+2))});
                        }
                    }

                    if (c >= 1 && r < (matrix.GetLength(0) - 1))
                    {
                        if (matrix[r, c] == matrix[r + 1, c - 1])
                        {
                            listTwice.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r+1),(byte)(c-1))});
                        }
                    }

                    if (r < matrix.GetLength(0) - 1)
                    {
                        if (matrix[r, c] == matrix[r + 1, c])
                        {
                            listTwice.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r+1),(byte)(c))});
                        }
                    }

                    if (r < (matrix.GetLength(0) - 1) && c < (matrix.GetLength(0) - 1))
                    {
                        if (matrix[r, c] == matrix[r + 1, c + 1])
                        {
                            listTwice.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r+1),(byte)(c+1))});
                        }
                    }

                    if (c < (matrix.GetLength(1) - 1))
                    {
                        if (matrix[r, c] == matrix[r, c + 1])
                        {
                            listTwice.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r),(byte)(c+1))});
                        }
                    }



                    if (c >= 2 && r < (matrix.GetLength(0) - 2))
                    {
                        if (player == matrix[r + 1, c - 1] && matrix[r, c] == matrix[r + 2, c - 2])
                        {
                            listTwice.Add(new List<Coordinates>(){new Coordinates(r,c),                                                             
                                                             new Coordinates((byte)(r+2),(byte)(c-2))});
                        }
                    }

                    if (r < matrix.GetLength(0) - 2)
                    {
                        if (player == matrix[r + 1, c] && matrix[r, c] == matrix[r + 2, c])
                        {
                            listTwice.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r+2),(byte)(c))});
                        }
                    }

                    if (r < (matrix.GetLength(0) - 2) && c < (matrix.GetLength(1) - 2))
                    {
                        if (player == matrix[r + 1, c + 1] && matrix[r, c] == matrix[r + 2, c + 2])
                        {
                            listTwice.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r+2),(byte)(c+2))});
                        }
                    }

                    if (c < (matrix.GetLength(1) - 2))
                    {
                        if (player == matrix[r, c + 1] && matrix[r, c] == matrix[r, c + 2])
                        {
                            listTwice.Add(new List<Coordinates>(){new Coordinates(r,c),
                                                             new Coordinates((byte)(r),(byte)(c+2))});
                        }
                    }
                    listSingle.Add(new List<Coordinates>() { new Coordinates(r, c) });

                }
            }
            #endregion
            if (listTriple.Count > 0)
            {
                return listTriple;
            }

            if (listTwice.Count > 0)
            {
                return listTwice;
            }

            return listSingle;

        } 
        #endregion


        static void PrintMatrix()
        {
            foreach (Coordinates item in bMove.listOfCoord)
            {
                matrix[item.Row, item.Col] = charPlay;
            }
            for (int rows = 0; rows < matrix.GetLength(0); rows++)
            {
                for (int cols = 0; cols < matrix.GetLength(1); cols++)
                {
                    Console.Write(matrix[rows, cols]);
                }
                Console.WriteLine();
            }
        }
    }

 
}
struct Coordinates
{
    byte row;

    public byte Row
    {
        get { return row; }
        set { row = value; }
    }
    byte col;

    public byte Col
    {
        get { return col; }
        set { col = value; }
    }
    public Coordinates(byte row, byte col)
    {
        this.row = row;
        this.col = col;
    }
}
struct BestMove
{
    public int moveScore;
    public List<Coordinates> listOfCoord;

    public BestMove(int score, List<Coordinates> list)
    {
        this.moveScore = score;
        this.listOfCoord = list;
    }
}

